#include<stdio.h>
#include<malloc.h>
#define MAX 100
typedef char ElemType;
typedef struct LNode
{	ElemType data;
	struct LNode * next;
}LinkNode;
typedef struct
{
	double coef;
	int exp;
}PolyArray;
typedef struct pnode
{
	double coef;
	int exp;
	struct pnode *next;
}PolyNode;
void CreateListF(LinkNode *&L,ElemType a[],int n)
{
	LinkNode *s;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->next= NULL;
	for (int i=0;i<n;i++)
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s->data=a[i];
		s->next=L->next;
		L->next=s;
	}
}
void CreateListR(LinkNode * &L,ElemType a[],int n)
{
	LinkNode *s,*r;
	L=(LinkNode *)malloc(sizeof(LinkNode));
	L->next=NULL;
	r=L;
	for(int i=0;i<n;i++)
	{
		s=(LinkNode *)malloc(sizeof(LinkNode));
		s-> data=a[ i];
		r ->next=s;
		r=s;
	}
	r->next==NULL; 
}
void DispPoly(PolyNode*L)
{
	bool first=true;
	PolyNode*p=L->next;
	while(p!=NULL)
	{
		if (first)
			first=false;
		else if(p->coef>0)
			printf("+");
		if(p->exp==0)	
			printf("%g",p->coef);
		else if(p->exp==1)
			printf("%gx",p-> coef);
		else
			printf("%gx ^%d",p->coef,p->exp);
		p=p->next;
	}
	printf("\n");
}
void DestroyPoly(LinkNode * &L)
{
	LinkNode *pre=L,*p=pre->next;
	while (p!=NULL)
	{
		free(pre);
		pre=p;
		p=pre->next;	
	}
	free(pre);
}
void Sort(PolyNode*&L)
{
	PolyNode*p=L->next,*pre,*q;
	if (p!=NULL)
	{
		q=p->next;
		p->next=NULL;
		p=q;
		while(p!=NULL)
		{
			q=p->next;
			pre=L;
			while(pre->next!=NULL && pre->next->exp>p->exp)
				pre=pre->next;
			p->next=pre->next;
			pre->next=p;
			p=q;
		}
	}
}

void Mult1(PolyNode*ha,PolyNode*hb,PolyNode*&hc)
{
	PolyNode*pa=ha->next,*pb,* s,* tc;
	hc=(PolyNode *)malloc(sizeof(PolyNode));
	tc=hc;
	while (pa!=NULL)
	{
		pb=hb->next;
		while(pb!=NULL)
		{
			s=(PolyNode *)malloc(sizeof(PolyNode));
			s->coef=pa-> coef *pb-> coef;
			s->exp=pa->exp+pb->exp;
			tc->next= s;
			tc=s;
			pb=pb->next;
		}
		pa=pa->next;
	}
	tc->next=NULL;
} 
void Comb(PolyNode*&L)
{
	PolyNode*pre=L->next,*p;
	if(pre==NULL)return;
	p=pre->next;
	while(p!=NULL)
	{
		while(p->exp==pre->exp)
		{
			pre->coef+=p->coef;
			pre->next=p->next;
			free(p);
			p=pre->next;
		}
		pre=p;
		p=p->next;
	}
}
void DelZero(PolyNode*&L)
{
	PolyNode*pre=L,*p=pre->next;
	while(p!=NULL)
	{
		if(p->coef==0.0)
		{
			pre->next=p->next;
			free(p);
		}
		pre=p;
		p=p->next;
	}
}
void Mult(PolyNode*ha,PolyNode*hb,PolyNode*&hc)
{
	Mult(ha,hb,hc);
	printf("相乘结果:");DispPoly(hc);
	Sort(hc);
	printf("按指数排序后:");DispPoly(hc);
	Comb(hc);
	printf("合并指数相同的项:");DispPoly(hc);
	DelZero(hc);
	printf("删除系数为0的项:");DispPoly(hc);
}
int main()
{
	PolyNode*Poly1,*Poly2,Poly3;
	double a[MAX];
	int b[MAX],n;
	a[0]=2;b[0]=3;a[1]=1;b[1]=0;a[2]=3;b[2]=1;
	n=3;
	printf("第1个多项式:\n");
	CreatePolyR(Poly1,a,b,n);
	printf("排序前多项式1:");DispPoly(Poly1);
	Sort(Poly1);
	printf("排序后多项式1:");DispPoly(Poly1);
	printf("第2个多项式:\n");
	a[0]=0;b[0]=3;a[1]=-3;b[1]=2;
	a[2]=5;b[2]=4;a[3]=-3;b[3]=0;
	n=4;
	CreatePolyR(Poly2,a,b,n);
	printf("排序前多项式2:");DispPoly(Poly2);
	Sort(Poly2);
	printf("排序后多项式2:");DispPoly(Poly2);
	Mult(Poly1,Poly2,Poly3);
	printf("相乘后多项式3:");DispPoly(Poly3);
	DestroyPoly(Poly1); 
	DestroyPoly(Poly2);
	DestroyPoly(Poly3);
	return 1;
}